package q198

//递归+map缓存
//递归过程中会有重复计算的路径，路径以剩余数为key，免除重复路径的计算

func rob(nums []int) int {

	var m map[int]int = map[int]int{}

	return recursion(nums, m)

}

func recursion(nums []int, m map[int]int) int {

	l := len(nums)

	value, ok := m[l]
	if ok {
		return value
	}

	if l <= 0 {
		return 0
	}
	if l == 1 {
		return nums[0]
	}

	var n1 int
	var n2 int

	if l == 2 {
		n1 = nums[0]
		n2 = nums[1]
	} else {
		n1 = nums[0] + recursion(nums[2:], m)
		n2 = recursion(nums[1:], m)
	}

	var max int
	if n1 >= n2 {
		max = n1
	} else {
		max = n2
	}
	m[l] = max
	//log.Printf("%v %v %d",nums,m,max);
	return max
}
